#pragma once
namespace yfy
{
	template<class T>
	struct __list_node		//list类中的节点结构体
	{
		//带默认参数的构造函数
		__list_node(const T& x = T())
			:_next(nullptr)
			,_prev(nullptr)
			,_data(x)
		{}
		__list_node<T>* _next;
		__list_node<T>* _prev;
		T _data;
	};

	template<class T, class Ref, class Ptr>
	struct __list_iterator		//list类中的迭代器结构体
	{
		typedef __list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		__list_iterator(Node* node)		//构造函数
			:_node(node)
		{}
		Ref operator*() {
			return  _node->_data;
		}
		Ptr operator->() {
			return &(_node->_data);
		}
		bool operator==(const self& it)const {
			return _node == it._node;
		}
		bool operator!=(const self& it)const {
			return _node != it._node;
		}
		self& operator++() {
			_node = _node->_next;
			return *this;
		}
		self operator++(int) {
			self tmp(*this);
			//self tmp(_node);
			_node = _node->_next;
			return tmp;
		}
		Node* _node;		//迭代器唯一的成员变量：__list_node<T>结构体对象的指针
	};

	template<class T>
	class list
	{
	public:
		typedef __list_node<T> Node;
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;
		list()
		{
			_head = new Node;		//调用__list_node<T>的构造函数
			_head->_next = _head;
			_head->_prev = _head;
		}
		template <class InputIterator>
			list(InputIterator first, InputIterator last) {
				_head = new Node;
				_head->_next = _head;
				_head->_prev = _head;
				while (first != last) {
					push_back(*first);
					first++;
				}
		}
		list(const list<T>& lt) {
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			list<T> tmp(lt.begin(), lt.end());
			std::swap(_head, tmp._head);
		}
		iterator begin() {
			return iterator(_head->_next);
		}
		iterator end() {
			return iterator(_head);
		}
		const_iterator begin()const {
			return const_iterator(_head->_next);
		}
		const_iterator end()const {
			return const_iterator(_head);
		}
		iterator insert(iterator pos, const T& val) {
			Node* newnode = new Node(val);
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			return iterator(newnode);
		}
		void push_back(const T& x) {
			insert(end(), x); 
		}
		iterator erase(iterator pos) {
			assert(pos != end());
			Node* cur = pos._node;
			Node* next = cur->_next;
			Node* prev = cur->_prev;
			delete cur;
			prev->_next = next;
			next->_prev = prev;
			return iterator(next);		//返回被删除节点的下一位置
		}
		void clear() {
			iterator it = begin();
			while (it != end()) {
				it = erase(it);
			}
		}
		list<T>& operator=(list<T> lt) {
			swap(_head, lt._head);
			return *this;
		}
	private:
		Node* _head;
	};

	void print_list(const list<int>& lt) {
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end()) {
			cout << *it << " ";
			it++;
		}
		cout << endl;
	}

	void test_list1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		print_list(lt);


		yfy::list<int>::iterator pos = std::find(lt.begin(), lt.end(), 2);

		if (pos != lt.end())
		{
			lt.insert(pos, 100);
		}

		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			//it.operator*() = 10;
			*it = 10;
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	struct TreeNode
	{
		struct TreeNode* _left;
		struct TreeNode* _right;
		int _val;

		TreeNode(int val = -1)
			:_left(nullptr)
			, _right(nullptr)
			, _val(val)
		{}
	};

	void test_list2()
	{
		list<TreeNode> lt;
		lt.push_back(TreeNode(1));
		lt.push_back(TreeNode(2));
		lt.push_back(TreeNode(3));
		lt.push_back(TreeNode(4));

		list<TreeNode>::iterator it = lt.begin();
		while (it != lt.end())
		{
			//cout << (*it)._val << " ";
			printf("val:%d,left:%p,right:%p\n", (*it)._val, (*it)._left, (*it)._right);
			printf("val:%d,left:%p,right:%p\n", it->_val, it->_left, it->_right);

			++it;
		}
		cout << endl;
	}

	void test_list3()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		print_list(lt);
		lt.clear();
		print_list(lt);

		lt.push_back(10);
		lt.push_back(20);
		lt.push_back(30);
		print_list(lt);
	}

	void test_list4()
	{
		list<int> lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;

		list<int> lt2(lt1);
		for (auto e : lt2)
		{
			cout << e << " ";
		}
		cout << endl;

		list<int> lt3(lt1.begin(), lt1.end());
		string s("hello");
		list<int> lt4(s.begin(), s.end());

		for (auto e : lt3)
		{
			cout << e << " ";
		}
		cout << endl;

		for (auto e : lt4)
		{
			cout << e << " ";
		}
		cout << endl;

		lt1 = lt4;

		for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}
